#include <vector>
#include <map>
#include <algorithm>

using namespace std;

//数组的相对排序
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> ans;
        map<int, int> _hash;
        sort(arr1.begin(), arr1.end());
        
        for (auto num : arr1)
        {
            ++_hash[num];
        }

        for (auto num : arr2)
        {
            while (_hash[num])
            {
                ans.push_back(num);
                --_hash[num];
            }
        }
        for (auto& hs : _hash)
        {
            while (hs.second)
            {
                ans.push_back(hs.first);
                --hs.second;
            }
        }
        return ans;
    }
};